package com.algorithm.dp;

import lombok.AllArgsConstructor;
import lombok.Data;
import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 背包问题:
 * 背包容量固定10,有几种物品可以装:A物品空间3价值2,B物品空间4价值5,C空间5价值7.怎么装能使背包里的价值最大化?
 */
public class SimplePack {

    public static void main(String[] args) {
        VO vo = getInput();
        pack01(vo.weights, vo.values,vo.capibility);
        pack02(vo.weights, vo.values,vo.capibility);
    }

    public static VO getInput() {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入背包大小:");
        String read = scan.nextLine();
        System.out.println("背包大小被设置为："+read);
        int capibility = Integer.valueOf(read);

        List<Integer> weightList = new ArrayList<>();
        List<Integer> valueList = new ArrayList<>();

        System.out.println("请输入物品重量和价值,以空格分割;空行结束");
        read = scan.nextLine();
        while(StringUtils.isNoneBlank(read)){
            System.out.println();
            String[] split = read.split(" ");
            String weight0 = split[0];
            String value0 = split[1];
            weightList.add(Integer.valueOf(weight0));
            valueList.add(Integer.valueOf(value0));
            read = scan.nextLine();
        }

        Integer[] weights = weightList.toArray(new Integer[weightList.size()]);
        Integer[] values = valueList.toArray(new Integer[valueList.size()]);
        return new VO(weights, values, capibility);
    }

    @Data
    @AllArgsConstructor
    static class VO{
        Integer[] weights;
        Integer[] values;
        int capibility;
    }


    public static void pack01(Integer[] weight, Integer[] value,int packSize) {
        Integer[][] arr = new Integer[weight.length][packSize +1];
        for (Integer[] integers : arr) {
            init(integers);
        }
        // i为当前物品,j为重量
        for (int j = 1; j < packSize +1; j++) {
            for (int i = 1; i < weight.length; i++) {
                int maxValueWithOutThisOne = arr[i - 1][j];
                int thisWeight = weight[i];
                if (j >= thisWeight) {
                    int subPackMax = arr[i - 1][j - thisWeight];
                    arr[i][j] = Math.max(value[i] + subPackMax, maxValueWithOutThisOne);
                } else {
                    arr[i][j] = maxValueWithOutThisOne;
                }
            }
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("背包最大值:"+arr[weight.length-1][packSize]);
    }


    // 使用一维数组解决背包问题 (实际上循环次数跟二维数组一样多)
    public static final void pack02(Integer[] weight, Integer[] value,int packSize){
        Integer[] arr = new Integer[packSize +1];
        init(arr);
        int count = 0;
        for (int j = 1; j < weight.length; j++) {
            for (int i = packSize; i >= 1; i--) {
                count++;
                Integer thisWeight = weight[j];
                Integer thisValue = value[j];
                findMaxValue(thisValue, arr, i, thisWeight);
            }
        }
        for (int i : arr) {
            System.out.print(i + "\t");
        }
        System.out.println(String.format("循环了%s次",count));
        System.out.println("背包最大值:"+arr[packSize]);
    }

    public static void init(Integer[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 0;
        }
    }

    public static void findMaxValue(Integer value, Integer[] arr,int i, Integer thisWeight) {
        if (i >= thisWeight){
            arr[i] = Math.max(arr[i],arr[i- thisWeight] + value);
        }else {
            arr[i] = arr[i];
        }
    }
}
